package demo;

import java.util.List;

public class Test {

    //10.环形链表2
    //返回入环的节点
    public static void main10(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(6);
        mySingleList.addLast(7);
        mySingleList.addLast(8);
        mySingleList.display();

        MySingleList mySingleList2 = new MySingleList();

        mySingleList2.addLast(5);
        mySingleList2.addLast(9);
        mySingleList2.addLast(11);
        mySingleList2.addLast(12);
        mySingleList2.addLast(15);
        mySingleList2.addLast(18);
        mySingleList2.display();
        System.out.println("------10. 环形链表2 ------");
        mySingleList.createLoop();
        MySingleList.ListNode node = mySingleList.detectCycle(mySingleList.head);
        System.out.println(node.val);
/*        1 2 6 7 8
        5 9 11 12 15 18
                ------10. 环形链表2 ------
        6*/

    }



    //9. 环形链表
    public static void main9(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(6);
        mySingleList.addLast(7);
        mySingleList.addLast(8);
        mySingleList.display();

        MySingleList mySingleList2 = new MySingleList();

        mySingleList2.addLast(5);
        mySingleList2.addLast(9);
        mySingleList2.addLast(11);
        mySingleList2.addLast(12);
        mySingleList2.addLast(15);
        mySingleList2.addLast(18);
        mySingleList2.display();
        System.out.println("------9. 环形链表 ------");
        mySingleList.createLoop();
        boolean ret = mySingleList.hasCycle(mySingleList.head);
        System.out.println(ret);
/*        1 2 6 7 8
        5 9 11 12 15 18
                ------9. 环形链表 ------
        true*/
    }



    //8. 相交链表
    public static  MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
      if(headA == null && headB == null){
          return null;
      }
        if(headA == null){
            return null;
        }
        if(headB == null){
            return null;
        }
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while(pl!=null){
            lenA++;
            pl = pl.next;
        }
        //要指回来!!!
        pl = headA;
        while(ps!=null){
            lenB++;
            ps = ps.next;
        }
        //要指回来!!!
        ps = headB;

        int len = lenA-lenB; //差值步
        if(len <0){
            pl = headB;
            ps = headA;
            len = lenB-lenA;
        }

        //1. pl永远指向最长的链表
        //   ps永远指向最短的链表
        //2. 求到了差值len步

        //pl走差值步
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //同时走 直到相遇
        //注意：不相遇的时候，pl和ps都会指向null的情况
        while(ps!=pl){
            pl = pl.next;
            ps = ps.next;
        }
/*        if(pl == null){
            return null;
        }*/

        return pl;

    }
    public static void  createCut(MySingleList.ListNode headA, MySingleList.ListNode headB){
        headA.next.next = headB.next.next.next;
    }

    public static void main8(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(6);
        mySingleList.addLast(7);
        mySingleList.addLast(8);
        mySingleList.display();

        MySingleList mySingleList2 = new MySingleList();

        mySingleList2.addLast(5);
        mySingleList2.addLast(9);
        mySingleList2.addLast(11);
        mySingleList2.addLast(12);
        mySingleList2.addLast(15);
        mySingleList2.addLast(18);
        mySingleList2.display();
        System.out.println("------8. 相交链表 ------");
        createCut(mySingleList.head,mySingleList2.head);
       try {
           MySingleList.ListNode ret = getIntersectionNode(mySingleList.head,mySingleList2.head);
           System.out.println(ret.val);
       }catch (NullPointerException e){
            e.printStackTrace();
           System.out.println("没有相交的节点");
       }


    }

    //7.删除链表中重复的值
    public static void main7(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(3);
        mySingleList.addLast(54);
        mySingleList.addLast(100);
        mySingleList.display();
        System.out.println("----------7. 删除链表中重复的值--------");
        MySingleList.ListNode node = mySingleList.deleteDuplication(mySingleList.head);
        mySingleList.display(node);
    }

    //6. 链表分割
    public static void main6(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(41);
        mySingleList.addLast(3);
        mySingleList.addLast(56);
        mySingleList.addLast(8);
        mySingleList.addLast(1);
        mySingleList.display();
        System.out.println("----------6. 链表分割--------");
        MySingleList.ListNode listNode = mySingleList.partition(10);
        mySingleList.display(listNode);
        System.out.println("----第二次---");
        MySingleList.ListNode listNode1 = mySingleList.partition(5);
        mySingleList.display(listNode1);
        System.out.println("---第三次----");
        MySingleList.ListNode listNode2 = mySingleList.partition(2);
        mySingleList.display(listNode2);
/*      ----------6. 链表分割--------
        1 3 8 1 41 56
         ----第二次---
        1 3 1 8 41 56
        ---第三次----
        1 1 3 8 41 56*/


    }

    //5. 链表的回文
    public static void main5(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(3);
        mySingleList.addLast(2);
        mySingleList.addLast(1);
        mySingleList.display();
        System.out.println("----------5. 链表的回文--------");
        System.out.println(mySingleList.chkPalindrome());

    }
    //4.合并两个有序链表
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {

        //获得了心态内部类对象 newHead
        MySingleList.ListNode newHead  = new MySingleList.ListNode(0);
        MySingleList.ListNode tmp = newHead;

        //1.两个链表都有数据的时候
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }else{
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }

        }

        if(list1!=null){
            tmp.next = list1;
        }

        if(list2!=null){
            tmp.next = list2;
        }

        return newHead.next;
    }
    public static void main4(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(6);
        mySingleList.addLast(7);
        mySingleList.addLast(8);
        mySingleList.addLast(10);
        mySingleList.display();

        MySingleList mySingleList2 = new MySingleList();

        mySingleList2.addLast(5);
        mySingleList2.addLast(9);
        mySingleList2.addLast(11);
        mySingleList2.addLast(12);
        mySingleList2.addLast(15);
        mySingleList2.addLast(18);
        mySingleList2.display();

        System.out.println("--------4. 合并两个有序链表--------");
        MySingleList.ListNode node = mergeTwoLists(mySingleList.head,mySingleList2.head);
        mySingleList2.display(node);


    }
    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);
        mySingleList.addLast(6);
        mySingleList.display();
        System.out.println("--------3. 链表中倒数第k个节点--------");
        MySingleList.ListNode node = mySingleList.findKthToTail(2);
        System.out.println(node.val);
    }
    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);
        mySingleList.addLast(6);
        mySingleList.display();
        System.out.println("--------2. 链表中的中间节点--------");
        MySingleList.ListNode node = mySingleList.middleNode(mySingleList.head);
        System.out.println(node.val);
    }



    public static void main1(String[] args) {

        MySingleList mySingleList = new MySingleList();

        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);

        mySingleList.display();
        System.out.println("--------1. 翻转链表--------");
       mySingleList.reverseList();
       mySingleList.display();
/*
  输出：
        1 2 3 4 5
                --------1. 翻转链表--------
        5 4 3 2 1*/
    }
}
